package main

import "fmt"

//44ms 96%，6.7MB 51%
func canJump(nums []int) bool {
	if len(nums) == 1 {
		return true
	}
	for i := 0; i < len(nums)-1; i++ {
		if nums[i] == 0 {
			flag := false
			for j := i - 1; j >= 0; j-- {
				if nums[j] > i-j {
					flag = true
					break
				}
			}
			if !flag {
				return false
			}
		}
	}
	return true
}

//贪心算法，实时维护最远可达位置,56ms 32%,6.7MB 82%
func canJump1(nums []int) bool {
	max := nums[0] + 1
	if max >= len(nums) {
		return true
	}
	for i := 1; i < len(nums); i++ {
		if max < i+1 {
			return false
		} else if nums[i]+i+1 > max {
			max = nums[i] + i + 1
		}
	}
	return true
}

func main() {
	fmt.Println((canJump([]int{1, 0, 3})))
	fmt.Println((canJump1([]int{1, 0, 3})))
}
